package leetcode.D700.D621;

import java.util.Arrays;

class Solution {
    /**
     * 桶思想：
     * - 相同的任务不能被放入同样的桶中，那么桶的数量就等于数量最多的任务的数量，这个数量（即桶的数量）记为N
     * - 除最后一个桶外，前面的桶最多只能装(n+1)个任务
     * - 最后一个桶比较特殊，它一定会装任务数最多的任务（任务数量最多的任务可能有多个，记为num个），且所有没有放完的任务，都可以一次性放到最后一个桶里
     * - 最短耗时 = (N - 1) * (n + 1) + 最好一个桶装的任务数量
     */
    public int leastInterval(char[] tasks, int n) {
        int[] cnt = new int[26];
        for (int i=0; i<tasks.length; ++i)
            cnt[tasks[i]-'A']++;
        Arrays.sort(cnt);
        int num = 0;
        for (int i=0; i<cnt.length; ++i) {
            if (cnt[i] == cnt[cnt.length-1])
                num++;
        }
        return Math.max(tasks.length, (cnt[cnt.length-1] - 1) * (n + 1) + num);
    }
}